package August;

import com.sun.jmx.snmp.SnmpNull;

import java.util.Scanner;


public class DAY0815 {
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] nums = new int[100001];
        nums[0] = 1;
        nums[1] = 1;
        for (int i = 2; i < 100001; i++) {
            nums[i] = (nums[i-1]+ nums[i-2])%1000000;
        }
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            if (n < 29)
                System.out.println(nums[n]);
            else
                System.out.printf("%06d\n",nums[n]);

        }
    }


}
